home *** CD-ROM | disk | FTP | other *** search
/ C & C++ Multimedia Cyber Classroom / C and C++ Multimedia Cyber Classroom (Prentice Hall) (1998).iso / src / fig04_20.jar / Ch04 / Fig04_20 / Fig04_20.cpp
C/C++ Source or Header  |  1997-10-13  |  2KB  |  85 lines
  1. // Fig. 4.20: fig04_20.cpp
  2. // Binary search of an array
  3. #include <iostream.h>
  4. #include <iomanip.h>
  5.  
  6. int binarySearch( int [], int, int, int, int );
  7. void printHeader( int );
  8. void printRow( int [], int, int, int, int );
  9.  
  10. int main()
  11. {
  12.    const int arraySize = 15;
  13.    int a[ arraySize ], key, result;
  14.  
  15.    for ( int i = 0; i < arraySize; i++ )
  16.       a[ i ] = 2 * i;   // place some data in array
  17.  
  18.    cout << "Enter a number between 0 and 28: ";
  19.    cin >> key;
  20.  
  21.    printHeader( arraySize );
  22.    result = binarySearch( a, key, 0, arraySize - 1, arraySize );
  23.  
  24.    if ( result != -1 )
  25.       cout << '\n' << key << " found in array element "
  26.            << result << endl;
  27.    else
  28.       cout << '\n' << key << " not found" << endl;
  29.  
  30.    return 0;
  31. }
  32.  
  33. // Binary search
  34. int binarySearch( int b[], int searchKey, int low, int high, 
  35.                   int size )
  36. {
  37.    int middle;
  38.  
  39.    while ( low <= high ) {
  40.       middle = ( low + high ) / 2;
  41.  
  42.       printRow( b, low, middle, high, size );
  43.  
  44.       if ( searchKey == b[ middle ] )  // match
  45.          return middle;
  46.       else if ( searchKey < b[ middle ] )
  47.          high = middle - 1;        // search low end of array
  48.       else
  49.          low = middle + 1;         // search high end of array
  50.    }
  51.  
  52.    return -1;   // searchKey not found
  53. }
  54.  
  55. // Print a header for the output
  56. void printHeader( int size )
  57. {
  58.    cout << "\nSubscripts:\n";
  59.    for ( int i = 0; i < size; i++ )
  60.       cout << setw( 3 ) << i << ' ';
  61.  
  62.    cout << '\n';
  63.  
  64.    for ( i = 1; i <= 4 * size; i++ )
  65.       cout << '-';
  66.  
  67.    cout << endl;
  68. }
  69.  
  70. // Print one row of output showing the current
  71. // part of the array being processed.
  72. void printRow( int b[], int low, int mid, int high, int size )
  73. {
  74.    for ( int i = 0; i < size; i++ )
  75.       if ( i < low || i > high )
  76.          cout << "    ";
  77.       else if ( i == mid )           // mark middle value
  78.          cout << setw( 3 ) << b[ i ] << '*';  
  79.       else
  80.          cout << setw( 3 ) << b[ i ] << ' ';
  81.  
  82.    cout << endl;
  83. }
  84.  
  85.